# -*- encoding: utf-8 -*-
'''
Filename         :grayCode.py
Description      :
Time             :2022/08/01 09:15:33
Author           :daiyizheng
Email            :387942239@qq.com
Version          :1.0
'''

from typing import List

# 规律题目
# 00  01
# 0   1
# 00  01   11  10    
# 0   1    3   2     
# 000  001  011  010  110 111  101  100 
# 0    1    3    2    6   7    5    4
# 下一个数组的后一半：对称反转+2的n-1次方
class Solution:
    def grayCode(self, n: int) -> List[int]:
        result = [0, 1]
        if n==1:
            return result
        for i in range(2, n+1):
            result += [2**(i-1) + x for x in reversed(result)]
        return result